home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / info-service / wais / ir-book-sources / bool / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-08  |  10.4 KB  |  459 lines
  1. /***************************  hashing-bool-ops.c  *****************************
  2.  
  3.   Purpose:    Hashing-based implementation of boolean operations.
  4.  
  5.   Provenance:    Written and tested by S. Wartik, April 1991.
  6.  
  7.   Notes:    None.
  8.  
  9. **/
  10.  
  11. #include    <stdio.h>
  12. #include    "hash.h"
  13.  
  14. static boolean error_occurred;    /* TRUE iff an error occurred on the    */
  15.                 /* last call to a boolean operator.    */
  16.  
  17. #define hash(s,e) (abs((*((s)->hashing_function))(e)) % (s)->Number_Of_Buckets)
  18.  
  19. extern char    *malloc();
  20.  
  21. /**************************************************************************
  22.  
  23.       Create(lower, upper, s)
  24.  
  25.   Returns:    void
  26.  
  27.   Purpose:    Create a hashing-based implementation of a set, using
  28.           application-provided specifications of the details
  29.         of hashing (function, comparison routine, and number of
  30.         buckets).
  31.  
  32.   Plan:        Set the values of "s" to the parameters, and allocate
  33.           global storage for the buckets.
  34.  
  35.   Notes:    This routine must be called before any of the other
  36.           routines (save error_occurred()) will work.
  37.  
  38. **/
  39.  
  40. void Create(Number_Of_Buckets, Hashing_Function, Comparator, s)
  41.     int     Number_Of_Buckets;
  42.     int     (*Hashing_Function)();
  43.     boolean (*Comparator)();
  44.     set     *s;
  45. {
  46.     register unsigned int    Bucket_Array_Size;
  47.     register int             i;
  48.  
  49.     if ( Number_Of_Buckets <= 0 ) {
  50.         error_occurred = TRUE;
  51.         return;
  52.     }
  53.     s->Number_Of_Buckets = Number_Of_Buckets;
  54.     s->hashing_function = Hashing_Function;
  55.     s->comparator = Comparator;
  56.     Bucket_Array_Size = sizeof(bucket_element) * Number_Of_Buckets;
  57.     s->buckets = (bucket_element **)malloc(Bucket_Array_Size);
  58.     if ( error_occurred = (s->buckets == NULL) )
  59.         return;
  60.     for ( i = 0; i < Number_Of_Buckets; i++ )
  61.         s->buckets[i] = (bucket_element *)NULL;
  62.  
  63. }
  64.  
  65. /**************************************************************************
  66.  
  67.       Clear(s)
  68.  
  69.   Returns:    void
  70.  
  71.   Purpose:    Indicate that set s is empty.
  72.  
  73.   Plan:        Set all buckets of s to NULL.
  74.  
  75.   Notes:    The Create() function does not automatically clear
  76.           a set; this routine must be called to do so.
  77.  
  78. **/
  79.  
  80. void Clear(s)
  81.         set     *s;
  82. {
  83.     register int            i;
  84.     register bucket_element *b, *next_b;
  85.  
  86.     for ( i = 0; i < s->Number_Of_Buckets; i++ )
  87.         if ( s->buckets[i] != NULL ) {
  88.             b = s->buckets[i];
  89.             while ( b != NULL ) {
  90.                 next_b = b->next_datum;
  91.                 free( (char *)b );
  92.                 b = next_b;
  93.             }
  94.             s->buckets[i] = NULL;
  95.         }
  96.     error_occurred = FALSE;
  97. }
  98.  
  99.  
  100. /**************************************************************************
  101.  
  102.       Insert(s, e)
  103.  
  104.   Returns:    void
  105.  
  106.   Purpose:    Insert element e into set s.
  107.  
  108.   Plan:        Hash the element to its bucket, and insert it into
  109.           the linked list for that bucket.
  110.  
  111.   Notes:    e may already be in s; if so, it is not added.
  112.  
  113. **/
  114.  
  115. void Insert(s, e)
  116.     set             *s;
  117.     elementType     e;
  118. {
  119.     register bucket_element *b, *New_Element;
  120.     register int            bucket;
  121.  
  122.     error_occurred = FALSE;
  123.  
  124.     bucket = hash(s,e);
  125.     for ( b = s->buckets[bucket]; b != NULL ; b = b->next_datum )
  126.         if ( (*(s->comparator))(b->datum, e) )
  127.             return;
  128.  
  129.     New_Element = (bucket_element *)malloc(sizeof (bucket_element));
  130.     if ( New_Element == NULL ) {
  131.         error_occurred = TRUE;
  132.         return;
  133.     }
  134.     New_Element->datum = e;
  135.     New_Element->next_datum = s->buckets[bucket];
  136.     s->buckets[bucket] = New_Element;
  137. }
  138.  
  139. /**************************************************************************
  140.  
  141.       Delete(s, e)
  142.  
  143.   Returns:    void
  144.  
  145.   Purpose:    Delete element e from set s.
  146.  
  147.   Plan:        Find the bucket in which e should reside, search for
  148.           it in the bucket's list, and, if it's there, remove
  149.         it from the list.
  150.  
  151.   Notes:    e doesn't have to be in s.
  152.  
  153. **/
  154.  
  155.  
  156. void Delete(s, e)
  157.         set             *s;
  158.         elementType     e;
  159. {
  160.     register bucket_element *b, *previous;
  161.     register int            bucket;
  162.  
  163.     error_occurred = FALSE;
  164.  
  165.     bucket = hash(s, e);
  166.     if ( (b = s->buckets[bucket]) == NULL )
  167.         return;
  168.     if ( (*(s->comparator))(b->datum, e) )
  169.         s->buckets[bucket] = b->next_datum;
  170.     else {
  171.         while ( b->next_datum != NULL ) {
  172.             if ( (*(s->comparator))(b->datum, e) )
  173.                 break;
  174.             previous = b;
  175.             b = b->next_datum;
  176.         }
  177.         if ( b == NULL )
  178.             return;
  179.         previous->next_datum = b->next_datum;
  180.     }
  181.     free( (char *)b );
  182. }
  183.  
  184. /**************************************************************************
  185.  
  186.       Empty(s)
  187.  
  188.   Returns:    boolean
  189.  
  190.   Purpose:    Determine whether a set is empty: return TRUE iff it is.
  191.  
  192.   Plan:        Any non-NULL bucket indicates the set is not empty; test
  193.           for that.
  194.  
  195.   Notes:    None.
  196.  
  197. **/
  198.  
  199.  
  200. boolean Empty(s)
  201.     set     *s;
  202. {
  203.     register int i;
  204.  
  205.     error_occurred = FALSE;
  206.     for ( i = 0; i < s->Number_Of_Buckets; i++ )
  207.         if ( s->buckets[i] != NULL )
  208.             return FALSE;
  209.     return TRUE;
  210. }
  211.  
  212. /**************************************************************************
  213.  
  214.       Member(s, e)
  215.  
  216.   Returns:    boolean
  217.  
  218.   Purpose:    Determine if e is a member of s: return TRUE iff it is.
  219.  
  220.   Plan:        Look for e in the list for bucket hash(s, e).
  221.  
  222.   Notes:    None.
  223.  
  224. **/
  225.  
  226.  
  227. boolean Member(s, e)
  228.         set             *s;
  229.         elementType     e;
  230. {
  231.     register bucket_element *b;
  232.     register int            bucket;
  233.  
  234.     error_occurred = FALSE;
  235.  
  236.     bucket = hash(s, e);
  237.     for ( b = s->buckets[bucket]; b != NULL ; b = b->next_datum )
  238.         if ( (*(s->comparator))(b->datum, e) )
  239.             return TRUE;
  240.     return FALSE;
  241. }
  242.  
  243. /**************************************************************************
  244.  
  245.       Unite(s1, s2, s3)
  246.  
  247.   Returns:    void
  248.  
  249.   Purpose:    Return in s3 the union of sets s1 and s2.
  250.  
  251.   Plan:        Copy s1 into s3, and then use Insert() to add
  252.           elements of s2 to s3.
  253.  
  254.   Notes:    None.
  255.  
  256. **/
  257.  
  258. void Unite(s1, s2, s3)
  259.     set     *s1, *s2;
  260.     set     *s3;
  261. {
  262.     register int            i;
  263.     register bucket_element *b;
  264.  
  265.     Copy(s1, s3);
  266.     if ( Error_Occurred() )
  267.         return;
  268.  
  269.     for ( i = 0; i < s2->Number_Of_Buckets; i++ ) {
  270.         if ( s2->buckets[i] == NULL )
  271.             continue;
  272.         for ( b = s2->buckets[i]; b != NULL; b = b->next_datum )
  273.             if ( ! Member(s3, b->datum) ) {
  274.                 Insert(s3, b->datum);
  275.                 if ( Error_Occurred() )
  276.                    return;
  277.         }
  278.     }
  279.     error_occurred = FALSE;
  280. }
  281.  
  282. /**************************************************************************
  283.  
  284.       Intersect(s1, s2, s3)
  285.  
  286.   Returns:    void
  287.  
  288.   Purpose:    Return in s3 the intersection of s1 and s2.
  289.  
  290.   Plan:        Clear s3.  Then, for each bucket in s1, search
  291.           through its elements, testing if each element is
  292.         in s2; if so, add that element to s3.
  293.  
  294.   Notes:    None.
  295.  
  296. **/
  297.  
  298. void Intersect(s1, s2, s3)
  299.     set     *s1, *s2;
  300.     set     *s3;
  301. {
  302.     register int            i;
  303.     register bucket_element *b;
  304.  
  305.     Clear(s3);
  306.  
  307.     for ( i = 0; i < s1->Number_Of_Buckets; i++ ) {
  308.         if ( s1->buckets[i] == NULL )
  309.             continue;
  310.         for ( b = s1->buckets[i]; b != NULL; b = b->next_datum )
  311.             if ( Member(s2, b->datum) ) {
  312.                 Insert(s3, b->datum);
  313.                 if ( Error_Occurred() )
  314.                     return;
  315.             }
  316.     }
  317.     error_occurred = FALSE;
  318. }
  319.  
  320. /**************************************************************************
  321.  
  322.       Subtract(s1, s2, s3)
  323.  
  324.   Returns:    void
  325.  
  326.   Purpose:    Return in s3 the difference between s1 and s2 (i.e., s1-s2).
  327.  
  328.   Plan:        Clear s3.  Then, for each element in s1, insert it in
  329.           s3 only if it's not in s2.
  330.  
  331.   Notes:    None.
  332.  
  333. **/
  334.  
  335. void Subtract(s1, s2, s3)
  336.     set     *s1, *s2;
  337.     set     *s3;
  338. {
  339.     register int            i;
  340.     register bucket_element *b;
  341.  
  342.     Clear(s3);
  343.  
  344.     for ( i = 0; i < s1->Number_Of_Buckets; i++ ) {
  345.         if ( s1->buckets[i] == NULL )
  346.             continue;
  347.         for ( b = s1->buckets[i]; b != NULL; b = b->next_datum )
  348.             if ( ! Member(s2, b->datum) ) {
  349.                 Insert(s3, b->datum);
  350.                 if ( Error_Occurred() )
  351.                     return;
  352.             }
  353.     }
  354.     error_occurred = FALSE;
  355. }
  356.  
  357. /**************************************************************************
  358.  
  359.       Copy(source, destination)
  360.  
  361.   Returns:    void
  362.  
  363.   Purpose:    Create a copy of a set.
  364.  
  365.   Plan:        Clear the destination set.  Then, for each element of
  366.           the source, create a copy by finding its hash address
  367.         in the destination and inserting it there.
  368.  
  369.   Notes:    The source and destination sets don't have to have the
  370.           same number of buckets.
  371.  
  372. **/
  373.  
  374. void Copy(source, destination)
  375.     set    *source, *destination;
  376. {
  377.     register int                i, h;
  378.     register bucket_element     *e, *b;
  379.     
  380.     Clear(destination);
  381.     for ( i = 0; i < source->Number_Of_Buckets; i++ ) {
  382.         if ( source->buckets[i] == NULL )
  383.             continue;
  384.         for ( b = source->buckets[i]; b != NULL; b = b->next_datum ) {
  385.             h = hash(destination, b->datum);
  386.             e = (bucket_element *)malloc(sizeof (bucket_element));
  387.             if ( e == NULL ) {
  388.                 error_occurred = TRUE;
  389.                 return;
  390.             }
  391.             e->datum = b->datum;
  392.             e->next_datum = destination->buckets[h];
  393.             destination->buckets[h] = e;
  394.         }
  395.     }
  396.     error_occurred = FALSE;
  397. }
  398.  
  399. /**************************************************************************
  400.  
  401.       Iterate(s, f)
  402.  
  403.   Returns:    void
  404.  
  405.   Purpose:    Perform some application-defined function f on each element
  406.           of set s.  The function f() should be of the form:
  407.  
  408.             boolean f(e)
  409.                 elementType    e;
  410.  
  411.         The iteration will continue as long as more elements
  412.         remain in the set and f() returns TRUE.
  413.  
  414.   Plan:        Scan the buckets in sequence; for each one that is not
  415.           NULL, invoke the iterator function supplied during
  416.         Create() on each element in that bucket's list.
  417.  
  418.   Notes:    There is no guaranteed order in which the elements are
  419.           passed to f().
  420.  
  421. **/
  422.  
  423. void Iterate(s, f)
  424.     set     *s;
  425.     boolean (*f)();
  426. {
  427.     register int            i;
  428.     register bucket_element    *b;
  429.  
  430.     error_occurred = FALSE;
  431.  
  432.     for ( i = 0; i < s->Number_Of_Buckets; i++ )
  433.     for ( b = s->buckets[i]; b != NULL; b = b->next_datum )
  434.             if ( ! (*f)(b->datum) )
  435.                 return;
  436. }
  437.  
  438. /**************************************************************************
  439.  
  440.       Error_Occurred()
  441.  
  442.   Returns:    boolean
  443.  
  444.   Purpose:    Indicate whether the last operation could not be
  445.           completed due to some error.
  446.  
  447.   Plan:        The routine's value is the value of the local variable
  448.           "error_occurred".
  449.  
  450.   Notes:    It is the responsibility of each routine to correctly
  451.           set "error_occurred".
  452.  
  453. **/
  454.  
  455. boolean Error_Occurred()
  456. {
  457.     return error_occurred;
  458. }
  459.